package twobranchTree.postorderTraversal;

import java.util.ArrayList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/11
 * @author 王光浩
 * @Description 给出一颗二叉树，对它进行后序遍历。
 * @Thinking 使用递归方法
 *           复杂度分析：时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodOne {
    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> result=new ArrayList<Integer>();
    	if(root!=null)postorder(root,result);
    	return result;
    }
    private void postorder(TreeNode node,List<Integer> result) {
    	if(node.left!=null)postorder(node.left,result);
    	if(node.right!=null)postorder(node.right,result);
    	result.add(node.val);
    }
    /**
     * 使用递归的方式进行后序遍历
     * @param root
     * @return
     */
    private List<Integer> ret = new ArrayList<Integer>();
    public List<Integer> postorderTraversal1(TreeNode root){
    	if (root == null)
    		return ret;
    	postorderTraversal(root.left);
    	postorderTraversal(root.right);
    	ret.add(root.val);
    	return ret;
    }
}
